package 算法.leetcode.labuladong.structure;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/6/23
 */
public class 基本计算器 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
//            System.out.println(solution.calculate("1 + 1"));
//            int amount = 0;
//            for (int i=1;i<=4;i++){
//                for (int j=1;j<=4;j++){
//                    for (int k=1;k<=4;k++){
//                        if (k!=i &&k!=j && i!=j){
//                            amount++;
//                        }
//                    }
//                }
//            }
//            System.out.println(amount);
//            int a = 19;
//            int b = 7;
//            int di = a/b;
//            int re=  a- (di*b);
//            System.out.println(re);
//            int n = 25;
//            int ctr = 0;
//            String bN = Integer.toBinaryString(n);
//            for (char ch: bN.toCharArray()){
//                ctr += ch =='0'?1:0;
//            }
//            System.out.println(ctr);
//            int n = 8;
//            int res = (n *(n+1)/2)*(1<<(n-1));
//
//            System.out.println(res);
//            int a = 7;
//            int sum = 0;
//            ArrayList<Integer> list = new ArrayList<>();
//            for (int i = 1; i <= a && sum < a; i++) {
//                for (int j = 0; j < i; j++) {
//                    list.add(i);
//                }
//                sum = sum + i;
//                if(sum == a) {
//                    break;
//                }
//            }
//            for (int i = 0; i < list.size(); i++) {
//                if(i == a-1) {
//                    System.out.println(list.get(i));
//                }
//            }
            int n = 3;
            int i=0;
            for (;i*(i+1)/2<n;i++){

            }
            System.out.println(i);
//            System.out.println(k);
        }

        LinkedList<Character> array;
        public int calculate(String s) {
            array = new LinkedList<>();
            for (Character c:s.toCharArray()){
                array.addLast(c);
            }
            return dfs();
        }

        public int dfs(){
            // 双端队列
            Stack<Integer> stk = new Stack<>();
            // 记录计算公式中的数字
            int num = 0;
            // 记录 num 前的符号，初始化为 +
            char sign = '+';
            while (!array.isEmpty()){
                Character c = array.pollFirst();
                if (isDigit(c)){
                    num = num * 10 + (c-'0');
                }
                // 处理括号 递归计算括号里面的
                if (c == '(') {
                    num = dfs();
                }
                if ((!isDigit(c)&& c !=' ') || 0==array.size()){
                    // 不是数字,不是空格或者最后的一个字符 标识着运算数扫描完成,需要将运算数入栈
                    int pre;
                    switch (sign){
                        case '+':
                            // 如果初始化为+号 且数字为负数开头,则先将0入栈
                            stk.push(num);
                            break;
                        case '-':
                            stk.push(-num);
                            break;
                        case '*':
                            pre = stk.pop();
                            stk.push(pre * num);
                            break;
                        case '/':
                            pre = stk.pop();
                            stk.push(pre / num);
                            break;
                    }
                    // 记录下个运算数之前的运算符
                    sign = c;
                    // 重新统计下一个运算数
                    num = 0;
                }
                // 遇到右括号 递归结束
                if (c == ')')break;

            }
            int res = 0;
            while (!stk.isEmpty()){
                res += stk.pop();
            }
            return res;
        }

        public boolean isDigit(char c){
            if (c>='0'&&c<='9')return true;
            return false;
        }
    }
}
